1. Field of the Invention
This invention relates to the field of computer graphics, and, more specifically, to graphical rendering of surfaces.
2. Background Art
In computer graphics, images are often created from three-dimensional objects modeled within a computer. The process of transforming the three-dimensional object data within the computer into viewable images is referred to as rendering. Typically, objects are modeled as one or more surfaces. Ideally, these surfaces comprise continuous curves for best visual realism. However, in practice, these surfaces are approximated with a mesh of less complex surface components, such as parametric surfaces or patches, to reduce the computational complexity of the rendering process. These patches are further subdivided or “diced” into triangles or polygons for rendering purposes. For example, bicubic patches are often rendered by subdividing their parameter space into rectangular grid of quadrilaterals, which are then further subdivided into triangles for rendering. A higher dicing rate provides greater modeling resolution and a better surface approximation. The dicing rate of a given patch may depend on factors such as the distance of the patch from the viewing plane and the local feature complexity of the patch.
An undesirable phenomenon known as “cracking” occurs when surfaces are split into multiple patches that are rendered independently. The shared boundaries between patches are tessellated and displaced by each side independently, which often creates narrow gaps or “cracks” between the two sides. Adjacent patches can compute different positions for their shared boundary curve for several reasons:                Two adjacent patches may dice at different rates, generating different numbers of vertices along a shared edge.        The adjacent patches may compute different positions for a vertex at the same parametric location, due to numerical errors. For example, this can occur if one patch has split into two pieces along the adjacent edge while the other patch has not.        Vertices along a shared edge may have different positions in the two patches due to displacement mapping (a technique whereby the diced vertex positions are modified according to a given formula, such as a texture map lookup, in order to add geometric detail to a smooth underlying surface). For example, this can happen when finite difference techniques are used in the displacement calculations (to estimate surface normals, derivatives, or texture filtering information). This is because finite difference techniques cause the position of a vertex to depend on the position of its neighbors, which are different in the two patch tessellations.        
An example of crack formation is illustrated in FIGS. 1A and 1B. FIG. 1A depicts an idealized surface comprising regions 100 and 101, having a continuous seam 102 between the regions. FIG. 1B depicts an approximation of the surface of FIG. 1A, wherein region 100 is now 100A comprising several parametric surfaces with piecewise linear edge 102A corresponding to seam 102. Similarly, region 101A comprises several parametric surfaces having piecewise linear edge 102B corresponding to seam 102. Edge 102A models seam 102 with higher dicing rate than edge 102B. As shown, edge 102A contains four vertices within the same span in which edge 102B has three vertices. The mismatch in dicing rates as well as the displacement differences between vertices in edges 102A and 102B form a crack 103 between regions 100A and 101A. Crack 103 represents a rendering error that may be visually apparent in the final rendered image, particularly where there is high contrast between the color value associated with regions 100A and 101A and the color value associated with the background visible through the crack.
Previous techniques for eliminating cracks fall into several categories. First there are methods that render parametric surfaces as a restricted quad-tree. That is, tessellation is limited to a pattern of quadrilaterals wherein the variation in dicing rates between patches is strictly constrained. These techniques store the entire tessellated surface in memory and do not support surfaces of arbitrary topology.
A second set of techniques are based on the idea that the tessellation of a boundary should be based only on the boundary curve itself. However, these methods do not eliminate all sources of cracking. In particular, if the patches on one side of a shared boundary have split more often than those on the other, then there is no single dicing rate for the unsplit patch that can match the multiple rates on the other side. Furthermore these techniques cannot handle the problems caused by displacement mapping, in which case the two sides can have different vertex positions even if the dicing rates match.
In another variation, the boundary curves are tessellated before patches are split. This technique has several drawbacks. It generates highly irregular tessellations that cannot be evaluated efficiently; it requires a substantial amount of time and memory to split patches that may eventually be occluded (and discarded) anyway; and, furthermore, this technique cannot render patches whose boundaries are simple (e.g. flat) but have complex features in their interiors.
Finally, some prior art techniques are based on the idea of splitting all patches and determining dicing rates in a preprocessing phase. For each portion of a shared boundary edge, one of the two adjacent patches is arbitrarily chosen to be associated with that edge. The main drawback to this approach is that the entire surface must be tessellated (or at least all dicing rates must be determined) in advance, which has significant time and memory expenses.